// 5. 最长回文子串/中心扩展法dp
//  https://leetcode.cn/problems/longest-palindromic-substring/
// 中等，给你一个字符串 s，找到 s 中最长的回文子串。
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
// 示例 1：
// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。
// 示例 2：
// 输入：s = "cbbd"
// 输出："bb"

#include <bits/stdc++.h>
using namespace std;
//  cbbd
//
class Solution{
public:
  string longestPalindrome(string s) {
    if(s.length()==1) return s;
    int maxLen = 1;
    int begin = 0;
    //dp[i][j]=s[i,j] is palidnrome
    vector<vector<int>> dp(s.length(), vector<int>(s.length()));
    for(size_t j=1; j<s.length();j++){
      for(size_t i=0; i<=j; i++) {
        if(s[i] == s[j]) {
          if (j-i < 2) {
            dp[i][j] = 1;
          } else {
            dp[i][j] = dp[i+1][j-1];
          }
        }
        if(dp[i][j] && j-i+1>maxLen) {
          maxLen = j-i+1;
          begin=i;
        }
      }
    }
    return s.substr(begin, maxLen);
  }
};
